package 纯数组;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class JZ57和为s的连续正数序列II {

    /**
     * 输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
     * 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
     *
     * 示例 1：
     * 输入：target = 9
     * 输出：[[2,3,4],[4,5]]
     * 示例 2：
     * 输入：target = 15
     * 输出：[[1,2,3,4,5],[4,5,6],[7,8]]
     *  
     * 限制：
     * 1 <= target <= 10^5
     */

    /**
     * 利用滑动窗口是最优解
     */
    public int[][] findContinuousSequence(int target) {

        List<int[]> resultList=new ArrayList<>();
        /**
         * 两个指针一起向右滑,一定都吃
         */
        int left=1;
        int right=2;
        int sum=left+right;

        while (right<target){

            if(sum<target){
                //右指针右移动
                right++;
                sum+=right;
            }else if(sum>target){
                //左指针左移动
                sum-=left;
                left++;
            }else{
                int[] arr=new int[right-left+1];
                for (int i = left; i <= right; i++) {
                    arr[i-left]=i;
                }
                resultList.add(arr);
                sum-=left;
                left++;
            }

        }

        int[][] result=new int[resultList.size()][];

        for (int i = 0; i < resultList.size(); i++) {
            result[i]=resultList.get(i);
        }
        return result;
    }

    public static void main(String[] args) {
        JZ57和为s的连续正数序列II jz=new JZ57和为s的连续正数序列II();
        int[][] result = jz.findContinuousSequence(9);
        System.out.println(JSON.toJSONString(result));
    }

}
